import java.util.Deque;
import java.util.LinkedList;

public class LC_239 {
    Deque<Integer> deque = new LinkedList<>();
    private void push(int val){
        while(!deque.isEmpty() && val > deque.getLast()){
            deque.removeLast();
        }
        deque.add(val);
    }

    private void pop(int val){
        if(!deque.isEmpty() && deque.peek() == val){
            deque.poll();
        }
    }

    private int getMax(){
        return deque.peek();
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length - k + 1;
        int[] arr = new int[len];
        for(int i = 0; i < len; i++){
            if(i == 0){
                while(i < k){
                    push(nums[i]);
                    i++;
                }
                i = 0;
            }else{
                pop(nums[i-1]);
                push(nums[i + k - 1]);
            }
            arr[i] = getMax();
        }
        return arr;

    }
}
